#include <iostream>
#include <string>
#include <map>
using namespace std;

string nums[4][9] = {{"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"M", "MM", "MMM"}};


class DicTree{
	struct TreeNode
	{
		int val;
		map<char,TreeNode*> children;
	};

public:
	DicTree(){
		pRoot = new TreeNode();
		pNow = pRoot;
		Init();
	}
	virtual ~DicTree(){};

	void Add(string &_str, int _val){
		TreeNode *pCur = pRoot;
		for(int i=0; i<_str.length(); ++i){
			char curCh = _str[i];
			map<char, TreeNode*>::iterator it = pCur->children.find(curCh);
			if(it != pCur->children.end()){
				// find
				pCur = it->second;
			}
			else{
				// not find
				TreeNode *newNode = new TreeNode();
				pCur->children[curCh] = newNode;
				pCur = newNode;
			}
		}
		pCur->val = _val;
	}

	bool Walk(char _ch, int &_val){
		map<char, TreeNode*>::iterator it = pNow->children.find(_ch);
		if(it != pNow->children.end()){
			// find, so walk
			pNow = it->second;
			return false;
		}
		else{
			// can not walk, not eat it
			_val = pNow->val;
			// reset
			pNow = pRoot;
			return true;
		}
	}
	void Init(){
		int base = 1;
		for(int i=0; i<3; ++i){
			for(int j=1; j<10; ++j){
				Add(nums[i][j-1], j*base);
			}
			base *= 10;
		}
		Add(nums[3][0], 1000);
		Add(nums[3][1], 2000);
		Add(nums[3][2], 3000);
	}
	void Reset(){
		pNow = pRoot;
	}
private:
	TreeNode *pRoot;
	TreeNode *pNow;
};

DicTree tree;

int romanToInt(string s) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int res = 0;
	int i = 0;
	tree.Reset();
	while(i<s.length()){
		char ch = s[i];
		int val = 0;
		if(!tree.Walk(ch, val)){
			++i;
		}
		else{
			res += val;
		}
	}
	int val = 0;
	tree.Walk('_', val);
	res += val;
	return res;
}



int main(){
	cout<<romanToInt("MMMCMXCIX")<<endl;
	return 0;
}